package leetcode.binaryTree;

import datastructure.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Description: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
 * @Author Ammar
 * @Create 2023/7/27 18:12
 */
public class _230_二叉搜索树中的第K小元素 {
    public int kthSmallest(TreeNode<Integer> root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            root = root.right;
        }
        return root.val;
    }
}
